package com.xcc.dataStructures.demo14_algapplication;

import java.util.ArrayList;
import java.util.List;

/**
 * 普里姆算法
 *  在图中以其中一个点作为开始顶点，最短距离连接所有的顶点
 *  最外层for为求每个边; 里面为双层for，第一层i为已经被访问,第二层j为未被访问，记录最短距离则是需要添加为访问的j
 */
public class Demo06_PrimAlgorithm {

    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}};


        MinTree minTree = new MinTree();
        minTree.createGraph(data, weight);
        minTree.showGraph();
        System.out.println("=============================");
        minTree.prim(4);

        prim(data,weight,4);


    }

    /**
     * prim算法(优化)
     *
     * @param data 顶点
     * @param weight 邻接矩阵
     * @param start 开始顶点
     */
    public static void prim(char[] data,int[][] weight,int start) {
        int length = data.length;
        //记录各最小节点的索引
        int[] indexArr = new int[length];
        //如果当前值为0 表示已经被访问， 其他情况表示未访问
        int[] visited = new int[length];

        //获取start这一行与其他节点的距离
        for (int i = 0; i < length; i++) {
            visited[i] = weight[start][i];
        }
        //标记start行为已访问
        visited[start] = 0;
        //记录第一个结点
        int index = 0;
        indexArr[index++] = start;


        int min;
        //记录
        int minIndex ;
        //记录权重
        int sum = 0;

        for (int i = 1; i <length; i++) {
            //记录每轮最小值
            min = 10000;
            //记录每轮的最小索引
            minIndex = -1;
            //获取visited中最小值（非零）
            for (int j = 0; j < length; j++) {
                if (visited[j] != 0 && visited[j] < min  ) {
                    min = visited[j];
                    minIndex = j;
                }
            }

            //证明这一轮没有最小索引,循环结束
            if (minIndex == -1) {
                break;
            }
            //记录(最小的索引)
            indexArr[index++] = minIndex;
            sum += min;

            //更新visited中的数据
            visited[minIndex] = 0;
            for (int j = 0; j < length; j++) {
                //如果当前visited数组中j的值  > 邻接矩阵中从minIndex到j的值  更新visited
                if (visited[j] != 0 && visited[j] > weight[minIndex][j]) {
                    visited[j] = weight[minIndex][j];
                }
            }
        }

        System.out.println("总的权重为: " + sum);
        for (int i = 0; i < length; i++) {
            System.out.printf("%s\t",data[indexArr[i]]);
        }
        System.out.println();

    }

    static class MinTree {

        Graph graph;

        /**
         * 构建最小生成树
         */
        public void createGraph(char[] data, int[][] weight) {
            graph = new Graph();
            graph.data = data;
            graph.weight = weight;
            graph.vertexNum = data.length;
        }

        /**
         * 普里姆算法
         *
         * @param start 起始位置索引
         */
        public void prim(int start) {
            //初始化各个顶点被访问状态
            int[] visited = new int[graph.vertexNum];

            //标记开始点已经被访问
            visited[start] = 1;
            //用x记录被已经被访问结点，用y表示当前步骤被访问的结点
            int x = -1;
            int y = -1;
            //最小权重
            int min;

            //最终会生成vertexNum-1条边，故而只需要遍历vertexNum-1次。当然也可以多遍历因为后面会有最小值的控制
            for (int k = 1; k < graph.vertexNum; k++) {
                min = 10000;
                //表示被访问的结点
                for (int i = 0; i < graph.vertexNum; i++) {
                    //表示未被访问的结点
                    for (int j = 0; j < graph.vertexNum; j++) {
                        //如果当前为i结点被访问，j结点为未被访问，当前路径权重小于最小权重
                        if (visited[i]==1 && visited[j]==0 && graph.weight[i][j] < min ) {
                            //此时记录最小权重，记录i结点和j结点
                            min = graph.weight[i][j];
                            x = i;
                            y = j;
                        }
                    }
                }

                //如果当前结点全部被访问，则min==10000，否则就有边未被访问。
                if (min < 10000) {
                    //记录当前y为被访问，并输出此时访问的边
                    visited[y] = 1;
                    System.out.println(getVertex(x) +" -> " +getVertex(y) +"  "+ min);
                }
            }


        }

        public char getVertex(int i) {
            return graph.data[i];
        }

        public void showGraph() {
            int[][] weight = graph.weight;
            for (int[] ints : weight) {
                for (int anInt : ints) {
                    System.out.printf("%5d\t", anInt);
                }
                System.out.println();
            }
        }
    }

    static class Graph {
        //定义顶点
        char[] data;
        //顶点数
        int vertexNum;
        //定义权重
        int[][] weight;
    }

}

